package other;

public class Fibonacci {

  /**
   * 递归 大量重复的计算 f（10）=f（9）+f（8）   f（9）=f（8）+f（7），消耗资源和时间
   */
  public long Fibonacci(int n) {
    if (n == 0) {
      return 0;
    }
    if (n == 1) {
      return 1;
    }
    return Fibonacci(n - 1) + Fibonacci(n - 2);
  }

  public long Fibonacci2(int n) {
    if (n == 0) {
      return 0;
    }
    if (n == 1) {
      return 1;
    }
    long f1 = 0;
    long f2 = 1;
    long result = 0;
    for (int i = 2; i <= n; i++) {
      result = f1 + f2;
      f1 = f2;
      f2 = result;
    }
    return result;
  }


  public static void main(String args[]) {
    Fibonacci fibonacci = new Fibonacci();
    long start = System.currentTimeMillis();
//        System.out.println(fibonacci.Fibonacci(40));
    System.out.println(fibonacci.Fibonacci2(40));
    long end = System.currentTimeMillis();
    System.out.println("耗费时间" + (end - start));
  }
}
